Java 中 LinkedList 的实现和排序源码学习

趁着今天有时间，记录一下。

前天闲逛 Leetcode 看到的一个排序 Linked List 的问题，然后自己尝试实现了一个不符合时间复杂度要求的。问题如下：

Sort a linked list in O(n log n) time using constant space complexity.

我是用递归实现的，没有通过 OJ ，代码附在最后。

然后我就想到了 Java 自身能够排序 Linkedlist 啊，调用 Collections.sort() 就行了啊，于是就找了源码看看，这才是这次要记录的重点。
看 Java 是怎么实现的 Linkedlist ，怎么对他排序的。

实验代码

首先贴上的是实验性质的代码，然后就能顺藤摸瓜，找到关键的排序代码。

package test;

import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;

public class LinkedListInJava {
    public static void main(String[] args) {
        LinkedList<Integer> linkeds = new LinkedList<Integer>();
        linkeds.add(5);
        linkeds.add(7);
        linkeds.add(1);
        linkeds.add(4);
        linkeds.add(2);
        Collections.sort(linkeds);
        Iterator<Integer> i = linkeds.iterator();
        while(i.hasNext()){
            System.out.println(i.next());
        }
    }
}

Java 自带的 LinkedList 实现

Java 实现了 LinkedList，看代码就能看到，是在 Util 包下的。那么它的内部实现是什么样子的呢？上代码：

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    //属性
    private transient Entry<E> header = new Entry<E>(null, null, null);
    private transient int size = 0;
    //构造方法，一个空的双向循环链表
    public LinkedList() {
        header.next = header.previous = header;
    }
    //构造方法，将传进来的元素加入链表
    public LinkedList(Collection<? extends E> c) {
        //调用默认无参的构造方法
true    this();
true    //添加已有的元素
true    addAll(c);
    }
    //省略其他方法 
}

看起来很简单，就记录了一个 header 和 size ，那么存放在 LinkedList 的数据呢，自然就可以通过 header 然后不断的 next 得到。

header 是一个 Entry 类型的属性，那么它才是能够代表 Linked list 存放数据的方法的主角。

//一个内部类
private static class Entry<E> {
    /*存放的值*/
trueE element;
true//下一个节点
trueEntry<E> next;
true//前一个节点
trueEntry<E> previous;
    
    //默认实现的构造方法
trueEntry(E element, Entry<E> next, Entry<E> previous) {
true    this.element = element;
true    this.next = next;
true    this.previous = previous;
true}
}

从这个 Entry 类的实现可以看出默认实现的LinkedList 是一个双向循环链表哦。具体的其他细节略过不表。

LinkedList<Integer> linkeds = new LinkedList<Integer>(); 就是一个初始化的过程
执行的是无参的构造方法。

然后是 add() ：

 public boolean add(E e) {
    //将元素放在 header 的前面，即下一个元素
trueaddBefore(e, header);
    return true;
    }

//双向循环链表插入一个元素（很好的实现例子）
 private Entry<E> addBefore(E e, Entry<E> entry) {
trueEntry<E> newEntry = new Entry<E>(e, entry, entry.previous);
truenewEntry.previous.next = newEntry;
truenewEntry.next.previous = newEntry;
truesize++;
true//这是父类的一个元素
truemodCount++;
truereturn newEntry;
    }

然后就是依次向这个双向的循环链表中插入5,7,1,4,2这些元素啦。

Linked list 的排序

排序才是重点，下面上代码：

 public static <T extends Comparable<? super T>> void sort(List<T> list) {
    //先把 list 转成一个数组，就是不断的把元素取出来，依次放进数组
trueObject[] a = list.toArray();
    //排序这个数组
trueArrays.sort(a);
true//把数组重新依次放进 list 里面
trueListIterator<T> i = list.listIterator();
truefor (int j=0; j<a.length; j++) {
true    i.next();
true    i.set((T)a[j]);
true}
}

过程不复杂，下面是具体每步的过程

TOARRAY：
  public Object[] toArray() {
    //按照 size 创建数组
trueObject[] result = new Object[size];
        int i = 0;
        //取出元素，放进数组
        for (Entry<E> e = header.next; e != header; e = e.next)
            result[i++] = e.element;
    //返回结果
truereturn result;
    }
    
SORT：
//修改后的 归并排序 保证 O(n*logn) 的时间复杂度
public static void sort(Object[] a) {
        Object[] aux = (Object[])a.clone();
        mergeSort(aux, a, 0, a.length, 0);
}

/*
 * The sorting algorithm is a modified mergesort (in which the merge is
 * omitted if the highest element in the low sublist is less than the
 * lowest element in the high sublist).  This algorithm offers guaranteed
 * n*log(n) performance.
 * Src  is the source array that starts at index 0
 * Dest  is the (possibly larger) array destination with a possible offset
 * low  is the index in dest to start sorting
 * high  is the end index in dest to end sorting
 * off  is the offset to generate corresponding low, high in src
 */
  private static void mergeSort(Object[] src,
truetruetruetrue  Object[] dest,
truetruetruetrue  int low,
truetruetruetrue  int high,
truetruetruetrue  int off) {
trueint length = high - low;
true// Insertion sort on smallest arrays 规模较小的时候用插入排序
true//private static final int INSERTIONSORT_THRESHOLD = 7;
        if (length < INSERTIONSORT_THRESHOLD) {
            for (int i=low; i<high; i++)
                for (int j=i; j>low &&
truetruetrue ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
                    swap(dest, j, j-1);
            return;
        }
        // Recursively sort halves of dest into src
        int destLow  = low;
        int destHigh = high;
        low  += off;
        high += off;
        int mid = (low + high) >>> 1;
        mergeSort(dest, src, low, mid, -off);
        mergeSort(dest, src, mid, high, -off);

        // If list is already sorted, just copy from src to dest.  This is an
        // optimization that results in faster sorts for nearly ordered lists.
        if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
            System.arraycopy(src, low, dest, destLow, length);
            return;
        }

        // Merge sorted halves (now in src) into dest
        for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
            if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
                dest[i] = src[p++];
            else
                dest[i] = src[q++];
        }
    }

    /**
     * Swaps x[a] with x[b].
     */
    private static void swap(Object[] x, int a, int b) {
trueObject t = x[a];
truex[a] = x[b];
truex[b] = t;
    }

注释很详细，很明白，整个过程就是一个归并排序，在规模较小的情况下直接用的插入排序。

总结

Java 实现的 Linked list 还有很多东西这里没有提到，需要的时候再看。

这里实现的排序算法很不错。

PS.
其实这个题目一开始我也想到了归并排序能满足要求，但是最后答好题目不是我的主要目的，主要是快速实现这个目的，于是写了一个简单的，容易想到的递归版本，类似冒泡，哈哈。

public class LinkedListSort {
    public ListNode sortList(ListNode head) {
        if(head == null) return head;
        if (head.next != null) {
            compareAll(head);
            sortList(head.next);
        }
        return head;
    }
    
    private void compareAll(ListNode head) {
    if(head.next!=null){
        if(head.val > head.next.val){
            int tem  = head.val ;
            head.val = head.next.val;
            head.next.val = tem;
        }
        compareAll(head.next);
    }
    }
public static void main(String[] args) {
    ListNode node1 = new ListNode(5);
    ListNode node2 = new ListNode(1);
    node1.next = node2;
    ListNode node3 = new ListNode(4);
    node2.next = node3;
    ListNode node4 = new ListNode(2);
    node3.next = node4;
    
    ListNode node5 = new ListNode(6);
    node4.next = node5;
    ListNode head = new LinkedListSort().sortList(node1);
}
}

class ListNode {
    int val;
    ListNode next;
    public ListNode(int value) {
        this.val = value;
        next = null;
    }
}

Over.